#define _CRT_SECURE_NO_WARNINGS 1

#include<iostream>
#include<list>
#include<unordered_map>

using namespace std;

class LRUCache {
public:
    LRUCache(int capacity)
        :_capacity(capacity)
    {}

    int get(int key) {
        if (_table.count(key))
        {
            auto t = _table[key];
            _lru.splice(_lru.begin(), _lru, t);
            return t->second;
        }
        return -1;
    }

    void put(int key, int value) {
        if (_table.count(key))
        {
            _table[key]->second = value;
            auto t = _table[key];
            _lru.splice(_lru.begin(), _lru, t);
        }
        else 
        {
            if (_lru.size() == _capacity)
            {
                _table.erase(_lru.back().first);
                _lru.pop_back();
            }
            _lru.push_front({ key,value });
            _table[key] = _lru.begin();
        }
    }

private:
    list<pair<int, int>> _lru;
    unordered_map<int, list<pair<int,int>>::iterator> _table;
    int _capacity;
};

int main()
{
    LRUCache c(2);

    c.put(1, 1);
    c.put(2, 2);
    c.get(1);
    c.put(3, 3);

    c.get(2);
    c.put(4, 4);

    c.get(1);
    c.get(3);
    c.get(4);


    return 0;
}